/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:二叉树的最近公共祖先.java
 * Date:2021/02/18 14:20:18
 */

package org.bytedance.链表和数;

import java.util.LinkedList;

public class 二叉树的最近公共祖先 {


    private static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        二叉树的最近公共祖先 instance = new 二叉树的最近公共祖先();
        TreeNode treeNode = instance.nearstCommonParent(root, root.left.right.left, root.left.right);
        System.out.println(treeNode.value);


        treeNode = instance.nearstCommonParent(root, root.left, root.right.left);
        System.out.println(treeNode.value);

        instance.nearstCommonParentSolution2(root, root.left.right.left, root.left.right);
        instance.nearstCommonParentSolution2(root, root.left, root.right.left);


    }


    /**
     * @param root
     * @param p
     * @param q
     * @return
     */
    public void nearstCommonParentSolution2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return;
        LinkedList<Integer> pPath = new LinkedList<>();
        LinkedList<Integer> qPath = new LinkedList<>();
        pPath.add(root.value);
        qPath.add(root.value);
        path(root, p, pPath);
        path(root, q, qPath);
        Integer res = null;
        for (int index = 0; index < pPath.size() && index < qPath.size(); index++) {
            if (pPath.get(index) == qPath.get(index)) res = pPath.get(index);
            else break;
        }
        System.out.println(res);
    }

    private boolean path(TreeNode root, TreeNode q, LinkedList<Integer> path) {
        if (root == q) return true;
        if (root.left != null) {
            path.add(root.left.value);
            if (path(root.left, q, path)) return true;
            path.removeLast();
        }
        if (root.right != null) {
            path.add(root.right.value);
            if (path(root.right, q, path)) return true;
            path.removeLast();
        }
        return false;
    }


    /**
     * 递归方法调用
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode nearstCommonParent(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = nearstCommonParent(root.left, p, q);
        TreeNode right = nearstCommonParent(root.right, p, q);
        return left != null && right != null ? root : left == null ? right : left;

    }
}
